Color printing is typically carried out by printing three or four color separations, (eg. cyan, magenta, yellow and black). Intermediate colors are made by printing mixtures of various amounts of these primary colors. It is possible, however, to specify pairs of colors that have little or no common components. For example, pure cyan and pure magenta, or an orange made from yellow and some magenta and a dark cyan made from cyan and black If adjacent areas of an image use two such colors, then a potential problem arises. The problem occurs if the registration between color components is not perfect. If the color separations are not perfectly aligned, then a gap can occur at the boundary between the two colors and the white of the paper can show through. This is considered objectionable and a technique known as trapping is used to reduce it. Trapping is usually thought of as moving the boundary for one of the colored areas so that it overlaps the neighboring area. If one is dealing with graphical objects, this amounts to spreading or bloating an object, or in choking or shriking its background
The layout of a page or graphic image depends upon combining "structured graphics" according to a pre-established graphic design The structured graphics are contiguous regions of color, usually represented in a plurality of separation images, which represent a succession of graphic objects imaged on the printing medium (e.g. the "paper"). The objects so imaged are shapes which can be isolated from each other, can abut one another at one or more points, can partially overlap one another, or can completely overlap one another. The resulting printed page or graphic image is therefore made up of a patchwork of shapes representing the graphic objects, some of which are "clipped" by objects imaged later in the succession.
The result of abutting or overlapping shapes is a boundary between adjacent regions of color which, under ideal printing conditions should have zero width. That is, the one color should stop exactly where the other begins, with no new colors introduced along the boundary by the printing process itself. The "colors" which fill the shapes can be solid colors, tints, degrades, contone images, or "no fill" (i.e., the paper with no ink applied). In general, the "colors" represented in these adjacent regions are printed using more than one colorant. In practice therefore, the realization of a zero width boundary between regions of different color is impossible as a result of small but visible misregistration problems from one printed separation to another. The error is manifested as a "light leak" or as a visible boundary region of an undesired color.
The problem of misregistration is a mechanical problem, almost always existing in printing systems. The problem arises because color separations are not laid exactly where intended, due to inherent imperfections in any separation registration process. It is somewhat correctable by mechanical registration methods; however it is rarely completely correctable. In expensive, high end printing processes, customers have high expectations that misregistration artifacts will not be visible. In inexpensive, low end printers, mechanical registration techniques are so expensive as to make correction or trapping essential.
As will become apparent, different printing technologies have distinct misregistration artifacts. Offset printing tends to have uniform misregistration in all directions. However, xerographic printing tends to have misregistration primarily in a single direction.
Methods for correcting for this misregistration are known in the prior art. The general approach is to expand one of the regions which abut so as to fill the gap or misregistration border region with a color determined so as to minimize the visual effect when printed Borders which are expanded from a region of one color to another in this manner are said to be "spread". A border which has been so expanded is referred to as a "trap", and the zone within which color is added is called the "trap zone".
Commonly used methods for automatic trapping of digital images fall into the categories of vector-based and raster-based methods. Vector-based methods rely on images that have been converted from a page-description language form, describing objects as characters, polygonal shapes, etc. into an internal data structure containing not only object information, but also a list of all the edges between regions of different color. Raster-based methods rely on images that have been first scanned or converted for page-description based form and are stored internally as a sequence of (high resolution) scan lines each containing individual scan elements or pixels. These methods process each raster line in sequence and compare one or more adjacent pixels to determine color boundaries. After some initial processing to find edges, both vector-based and raster-based methods apply rules for determining whether or not to create a trap at such boundaries, and finally apply a second set of rules to determine the nature of the trap if one is to be created.
Thus, it can be seen that most trapping processes takes the following format which shall be referenced throughout this discussion
A. Find edges in the image, no matter how described; PA1 B. For each pair of colors on each side of the found edge, determine: PA1 Modify the image accordingly. PA1 component-wise maximum color differences are determined for each pixel from neighboring pixels; and PA1 a fraction of said difference is then added to said pixel's color value. A difference between a pixel (pixel a) value and its set of neighboring pixels (pixel ith) is calculated and the value of pixel a is modified, said change effected by adding a fraction of color components Cx, Mx, Yx, Kx to the colorant specification for pixel a (Ca, Ma, Ya, Ka), wherein the change values relate to the amounts of neighboring colorant that are missing from pixel a. The color difference is added in a fraction t so the modified pixel value will be given by Ca'=Ca +t=Cx, Ma'=Ma +t =Mx, Ya'=Ya +t =Yx, Ka'=Ka +t =Kx, wherein fraction t will depend upon a property of pixel a such as its luminance of pixel a
1) Whether trapping should be used, and PA2 2) choose a method of trapping.
The present invention differs from this prior art in that there is no explicit finding of edges (no step A). It also differs from step B in that it does not try to decide whether or not trapping should be used; instead, it always applies its modifications to every pixel. Furthermore, there is no selection of a trapping method; its single modification scheme is universally applied. In the prior art, the method of Taniguchi, described in US-A 4,931,861, uses two rasterized images representing abutting or overlapping objects within an image field to define a third binary image representing the map of the pixels which make up the borders between the first and second images. These three images are superimposed, pixel by pixel, to create a fourth and final binary image.
The method of Darby et at., described in US-A 4,725,966, again defined on a pixel basis, uses a mask which is moved, one resolution element at a time, to evaluate the presence or absence of (pixel) colors upon which a positive or negative spread decision is based.
The method of Yosefi, described in US-A 5,113,249 uses a set of automated rules as the basis for deciding, for each pair of abutting or overlapping shapes whether or not to create a trap (an overlap region referred to as a "frame"), and, if so, the nature of the trap to create. The preferred embodiment described by Yosefi makes use of scanned data, and processes each line of pixels in order, comparing for each pixel three pixels from the previous scan line and two pixels from the same line to determine if a color change has occurred The decisions regarding whether or not to create a trap, and the nature of such a trap if created are imbedded within the processing sequence, making use of criteria established prior to the onset of processing. Yosefi describes rules to follow after finding an edge and knowing the two colors. There are 24 rules based on whether the colors are tints, special colors like gold leaf), black, yellow, "window" (meaning scanned image) and various combinations.
A commercially available product, "TrapWlse", from Aldus Corporation, Seattle Wash., also makes use of a raster approach to trapping. In this product, the processing time is proportional to the number of resolution elements, thereby increasing quadratically with resolution, and leading to greater computation times for high device resolution, e.g., 3600 dots per inch (d.p.i.). Furthermore, traps are created with this package using pre-set rules, and are not editable by a user without the requirement for repeating the computation.
US-A 4,583,116 to Hennig el al describes a trapping process that evaluates the darkness on both sides of an edge in order to determine which object determines the contour. The object determining the contour is left unchanged. The other object is spread under it. The fill is constant, and matches the value of the separation being spread The "darkest" separation is used to determine the contour and kept constant, while the lighter separations are all spread
US-A 4,700,399 describes a method that finds edges and uses a different Undercolor Removal (UCR) scheme along the edges from elsewhere to allow rich black without getting color bleeding along the edges of black objects. The method requires keeping colors away from edges of black text
US-A 4,931,861 to Taniguchi describes using binary operators to shrink or spread a shape where another shape is overlapped in another separation (thresholding is used to get these shapes). Also described is spreading where two shapes are adjacent, and do not overlap.
US-A 5,131,058 to Ting et. al. converts a raster to an edge-based "outline" representation Then the outlines are spread and the resulting image is re-rasterized. Spreading is done separation-wise with a process indicating whether there is a color difference that warrants spreading/choking.
US-A 5,295,236 Bjorge, et. al. may represent the Adobe or Aldus TrapWise product described above. This patent describes ways of deriving the information about edges required to trap, trapping with some simple rules, and converting the traps to vectors which are converted back to PDL form.
US-A 5,204,918 to Hirosawa assumes vector data as input, describing the contours, i.e., no edge detection is performed. Image parts are selected in order of increasing priority. For parts of a contour of an image part where there is a lower priority image part adjacent, two supplemental contours are generated These are offsets at a specified distance from the original contour. A new color is computed for the entire offset region (both sides of the original, not just where there is another object). The maximum density of the two sides is used in the correction region. Minimum density might be used instead The edge following required is either done in a frame buffer, or directly on vector data.
US-A 5,402,530 to Boenke et al. uses a Page Description Language (PDL) input, and builds a data-structure using a modified Weiler algorithm to represent the contours. It is object-based, in that it considers four classes of object: interior fills, strokes on the borders of regions, text on top of regions, and text on its own.
US-A 5,386.223 to Saitoh et al. addresses two-color printing, extending one color into another where they abut It suggests that it is desirable to extend the lighter color.
US-A 5,542,052 to Deutsch, et. al claims a set of geometric rules. First, a relative darkness to each color is assigned, with magenta being the darkest color, cyan being a middle darkness color, and yellow being the lightest color. Then, the lighter color is spread under the darker color. A trap vector is drawn in a color which is a function of the two colors abutting each side of the edge.
US-A 5,313,570 to Dermer, et. al. takes either raster or PDL input, and creates an intermediate, vector-based form The manipulations themselves are based on a plane sweep algorithm generating a display list and then from that display list generating a new representation called a scan beam table. The active edge table has a polygon stack for each edge. From these representations, a boundary map is generated
US-A 5,668,931 to Dermer describes trapping rules. The overall concept is to have a set of evaluation methods, and for each candidate trap, let each of the evaluation method decide whether it is an optimum trap. Each method ranks all of the candidate traps, and then the traps are scored, using the weighted sum of the rankings. In this way some evaluation methods are more likely than others. Candidate traps appear to consist of the typical spreads and chokes, although they mention that reduced amounts are also possible The evaluation methods are as follows: 1) For each possible misregistration, determine the minimum distance in CIELUV from the two bounding colors, and then use the maximum of those minima as a score; 2) Determine the CIELUV distance from the trap color to the color into which it is spread; 3). For each misregistration, determine the difference in L* values from each of the bounding colors, with the score set as the maximum value of the set --i.e., favoring relatively darker misregistration colors; 4) For each misregistration color, determining the absolute difference in L* value from each bounding color, so that the score is based only on lightness differences; 5) Determine the L* value of each misregistration color, with the score indicating dark misregistration colors. 6) Determine the L* of the bounding colors and assign a score equal to the absolute difference in L* when a dark color is spread into a light, or zero when a light color is spread into a dark, penalizing the former; 7) Use the highest percentage of yellow in a misregistration color. The weights are determined empirically, and can be adjusted over time, or as a particular application demands. They are initially determined by a least squares process based on expert evaluation of a number of calibration traps.
US-A 5,613,046 to Dermer describes a user interface allowing the display of an image, and selection of any color, pair, object, edge or color and modification of the trapping behavior in terms of inward/outward, or what color, how automatic or manual to be, etc. It also allows display of the effect of any of the 16 possible misregistrations on the selected color pair, object, edge or color, with or without the current trapping applied, and to iterate through the possible modifications, applying several possible traps and see which is best
US-A 5,440,652 to Ting describes a process to find an edge and track it, building a secondary edge during processing. The secondary edge will be used as the other side of the trap region. The placement of the secondary edge and the color of the region between is determined by reference to a rule base.
US-A 5,615,314 to Schoenzeit et al. describes a basic architecture for a RIP - printer interface. It includes buffering and queues and compression for transferring page images to the printer from the RIP. It also has control information, in particular, multiple copy and abort instructions. It also provides an optional dilation processor which "selectively dilates objects" in order to compensate for potential misregistration errors. There is no indication of how it selects. It dilates using "standard convolution techniques" such as taking the max of a 3.times.3 neighborhood.
US-A 5,513,300 to Shibazaki describes trapping rasters against line art. They are concerned with the image and line art being at different resolutions. Line art is stored as run length data, and images as raster. The method forms a mask indicating where the image appears, and erodes or dilates the mask The non-exempt separations of the image or line art are then copied into the eroded or dilated regions (respectively). A separation is exempt if the operator so indicates.
US-A 5,386,483 to Shibazaki discusses finding a trapping region in a raster-based image. The image is segmented into regions, each of a constant color. Each such region is assigned a region number, and a lookup table is used to store the correspondence between region number, and colors, including both CMYK, and RGB. RGB is used by the operator supervising the process with a display and mouse. The data is then run-length encoded, using runs of color table indices. The algorithm is multi-pass. On the first pass, an eight-neighbor window is used to form a pair of "frame" regions along each color boundary. On subsequent passes, a four-neighbor set is used to extend the frame region. Finally, a color is assigned to each new region thus formed. To form a "frame"region, a three scanline buffer is used The center pixel in a window is considered to be in the frame region if 1) the pixel is located in one of the original regions (i.e., not already in a frame region), and 2) at least one neighbor is in a different region. Regions/colors have priorities specified (by the user). When the neighbor with the highest priority is part of a frame, the frame number is used for the new region of the pixel. Otherwise, a new frame number is allocated and used It appears that priorities don't change when pixels are assigned to frame regions.
US-A 5,241,396 to Harrington describes a simple raster-based technique for protecting rich black text. Black separation images are eroded to and then ANDed with each of CMY, to produce new cyan, magenta and yellow separations. The original black is then used as the black separation.
US-A 4,700,399 to Yoshida finds edges and uses a different UCR along the edges from elsewhere to allow rich black without getting color bleeding along the edges of black objects. Colors are kept away from edges of black text.
US-A 5,666,543 to Gartland and US-A 5,542,052 describes an arrangement providing a prolog substituted to turn on trapping. The prolog instructs the Raster Image Processor (RIP) to build a "shape directory " and then to trap the objects in the shape directory. The shape directory appears to be a back-to-front display list. Objects are processed in the back-to-front order. If they overlap existing objects, they are trapped against thee If the existing object already has been trapped, the traps are undone before the new traps are introduced Thus traps are introduced as objects are processed, possibly causing a region to be trapped and re-trapped as the traps are covered up. The decision of whether to trap includes text point size and changes in separation strength.
The trapping methods described in the above cited prior art references have two common features: The first is that most process images represented in raster form and seek edges at which to apply their trapping. This places a requirement for extra processing steps in images which constitute primarily structured graphics or which combine structured graphics with contone images. Such images must first be rasterized at the output resolution, and then the appropriate line-scan algorithm applied. They must also employ some edge detection scheme to identify edges where trapping should occur.
The second common feature of prior art methods is the necessity to make and apply trapping decisions within the processing based upon pre-established criteria For raster based processing at high output device resolution, the potential number of pixel-to-pixel color transitions is large due to repetition of transitions corresponding to a single color region border shared by many scan lines.
Many rule-based methods exist in the prior art for automatic determination of the particular trap to be specified for a given combination of bounding colors. For example, in U.S. Pat No. 5,113,249 to Yosefi, a set of logical tests is used in sequence to differentiate between pre-established generic color-pair categories, with a rule applied to each color pair. Such built-in rule systems attempt to replicate the human aesthetic judgment used in manual specification of traps and each can provide results satisfactory to an "expert" user in most cases while failing to do so in other special situations. The specification of a trap at the boundary between two color regions does not in itself eliminate the misregistration of printing plates, but reduces the visual effect of misregistration within the trap zone through proper choice of the trap operation. In the event of plate misregistration involving a color separation for which a trap has been specified, additional "secondary" effects occur.
The above patents and particularly US-A 5,313,570 and US-A 5,668,931 to Dermer, and US-A to Yosefi are hereby incorporated by reference for their teachings.